package array

func canPartition(nums []int) bool {

	sum := 0
	for _, v := range nums {
		sum += v
	}

	if sum%2 == 1 {
		return false
	}
	target := sum / 2
	dp := make([]int, target+1)
	for _, num := range nums {
		for i := target; i >= num; i-- {
			if dp[i-num]+num > dp[i] {
				dp[i] = dp[i-num] + num
			}
		}
	}
	return dp[target] == target
}
